package leetcode;

import java.util.LinkedList;
import java.util.List;

/**
 * Created by Ghost on 2015/2/1.
 */
public class Valid_Sudoku {

    private boolean isAvalible(char[][] board, int r,int c){
        char i=board[r][c];
        int a = r/3,b=c/3;
        int beginX = 3*a,beginY = 3*b;
        int count=0;
        int j;
        for(j=0;j<board.length ;j++){
            if(j==c)
                continue;
            if(board[r][j]==(""+i).charAt(0))
                break;
        }
        if(j==board.length)
            count++;

        if(count==1){
            for(j=0;j<board.length;j++){
                if(j==r)
                    continue;
                if(board[j][c]==(""+i).charAt(0))
                    break;
            }
            if(j==board.length)
                count++;

            if(count==2){
                boolean flag=false;
                for(int cc=beginX;cc<beginX+3 && !flag;cc++)
                    for(int dd=beginY;dd<beginY+3 && !flag;dd++){
                        if(cc==r && dd==c)
                            continue;
                        if(board[cc][dd]==(""+i).charAt(0))
                            flag=true;
                    }
                if(!flag)
                    count++;
                if (count==3){
                    return true;
                }
            }

        }
        return false;
    }

    public boolean isValidSudoku(char[][] board) {
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board.length;j++){
                if(board[i][j]!='.'){
                    if(!isAvalible(board,i,j)){
                        return false;
                    }
                }
            }
        }
        return true;
    }
    public static void main(String[] args){
        Valid_Sudoku valid_sudoku = new Valid_Sudoku();
        char[][] board = {{'5','3','.','.','7','.','.','.','.'},
                          {'6','.','.','1','9','5','.','.','.'},
                          {'.','9','8','.','.','.','.','6','.'},
                          {'8','.','.','.','6','.','.','.','3'},
                          {'4','.','.','8','.','3','.','.','1'},
                          {'7','.','.','.','2','.','.','.','6'},
                          {'.','6','.','.','.','.','2','8','.'},
                          {'.','.','.','4','1','9','.','.','5'},
                          {'.','.','.','.','8','.','.','7','9'}};

        System.out.println(valid_sudoku.isValidSudoku(board));
    }
}
